package com.lihepeng.leecode.tree;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 中序遍历
 * 前-》根-》后
 * 2022年1月24日 复习
 */
public class InOrderTravel {
    // 中序遍历
    // 使用递归完成遍历

    public List<Integer> inorderTravel(TreeNode headNode) {
        List<Integer> resultList = new ArrayList<>();
        if (headNode == null) {
            return resultList;
        }
        resultList.addAll(inorderTravel(headNode.left));
        resultList.add(headNode.val);
        resultList.addAll(inorderTravel(headNode.right));
        return resultList;
    }

    // 借助于栈结构完成中序遍历
    public List<Integer> inorderTravel01(TreeNode headNode) {
        List<Integer> resultList = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(headNode);
        TreeNode curNode = headNode.left;
        while (!stack.isEmpty() || curNode != null) {
            // 将所有的左节点压入栈
            while (curNode != null) {
                stack.push(curNode);
                curNode = curNode.left;
            }
            // 出站进行遍历
            curNode = stack.pop();
            resultList.add(curNode.val);
            curNode = curNode.right;
        }
        return resultList;
    }

    /**
     * 中序遍历
     * root.val 在前面 左右子树在两侧
     * @param headNode
     * @return
     */

    public List<Integer> inorderTravel02(TreeNode headNode) {
        List<Integer> list = new ArrayList<>();
        if (headNode ==null) {
            return list;
        }
        inorderTravel02(headNode.left);
        list.add(headNode.val);
        inorderTravel02(headNode.right);
        return list;
    }
    @Test
    public void runTest() {
        TreeNode head = new TreeNode(0);
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        head.left = n1;
        head.right = n2;
        n1.left = n3;
        n1.right = n4;
        n2.left = n5;
        List<Integer> list = inorderTravel01(head);
        System.out.println(list);
    }
}
